package 排序;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @Author: WangYongGan
 * @Date: 2021/11/9 14:21
 * @Description:
 */
public class binaryFind {
    /**
     * @Description: 二分查找，找到返回下下表，找不到:应该插入的位置x 返回-x-1
     * @Params: 返回y   应该插入位置-y-1
     * @return:
     **/
    public static int find(Integer nums[], int n) {
        int begin = 0;
        int end = nums.length - 1;
        while (begin <= end) {
            int mid = (int) ((begin + end) / 2);
            if (nums[mid] == n)
                return mid;
            if (nums[mid] > n) {
                end = mid - 1;
            } else begin = mid + 1;
        }
        return begin;
    }

    public static void main(String[] args) {
//        int[] nums = new int[10];
//        Random random = new Random();
//        for (int i = 1; i < 10; i++)
//            nums[i] = nums[i - 1] + random.nextInt(5) + 1;
//        nums = new int[]{1, 3, 4, 8, 13, 14, 16, 20, 22, 25};
        Integer[] nums = new Integer[]{1, 2, 4, 8, 16};
        for (int i = 1; i < nums.length; i++) {
            nums[i] = nums[i - 1] + nums[i];
        }
        System.out.println(find(nums, 27));
        System.out.print("原数组: ");
//        List<Integer> list = Arrays.stream(nums).mapToObj(o -> Integer.valueOf(o)).collect(Collectors.toList());
    }
}
